/*
 * @lc app=leetcode.cn id=2163 lang=typescript
 *
 * [2163] 删除元素后和的最小差值
 */

// @lc code=start

class Heap {
  n: number;
  data: number[];
  constructor() {
    this.n = 0;
    this.data = [];
  }

  private swap(i: number, j: number): void {
    [this.data[i], this.data[j]] = [this.data[j], this.data[i]];
  }

  private less(i: number, j: number): boolean {
    return this.data[i] < this.data[j];
  }

  private swin(i: number): void {
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (this.less(i, p)) {
        this.swap(i, p);
      } else {
        break;
      }
      i = p;
    }
  }

  private sink(i: number): void {
    while (i < this.n) {
      let j = (i << 1) + 1;
      if (j + 1 < this.n && this.less(j + 1, j)) {
        j++;
      }
      if (j >= this.n || this.less(i, j)) {
        break;
      }
      this.swap(i, j);
      i = j;
    }
  }

  insert(x: number): void {
    this.data.push(x);
    this.n++;
    this.swin(this.n - 1);
  }

  pop(): number {
    const x = this.data[0];
    this.swap(0, this.n - 1);
    this.data.pop();
    this.n--;
    this.sink(0);
    return x;
  }

  clear(): void {
    this.n = 0;
    this.data = [];
  }
}

function minimumDifference(nums: number[]): number {
  let m = nums.length;
  let n = m / 3;
  // 默认小顶堆
  let heap = new Heap();
  // 左边区间内可以减少的最大值
  const lsum = new Array(m).fill(0);
  let ltotal = 0;
  for (let i = 0, sum = 0; i < m; i++) {
    ltotal += nums[i];
    // 需要取当前区间的最大值，所以用的负数
    heap.insert(-nums[i]);
    if (heap.n < n) continue;
    if (heap.n > n) {
      sum -= heap.pop();
    }
    lsum[i] = sum;
  }

  heap.clear();
  let rtotal = 0;
  let ans = Number.MAX_SAFE_INTEGER;
  for (let i = m - 1, sum = 0; i >= n; i--) {
    ltotal -= nums[i];
    rtotal += nums[i];
    // 需要取当前区间的最小值
    heap.insert(nums[i]);

    if (heap.n < n) continue;
    if (heap.n > n) {
      sum += heap.pop();
    }
    // 左边减去可以删除的最大值，右边减去可以删除的最小值
    // 这样两者之间的差值就是最小的
    ans = Math.min(ans, ltotal - lsum[i - 1] - (rtotal - sum));
  }

  return ans;
}
// @lc code=end
